import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
/*
 * @lc app=leetcode.cn id=496 lang=java
 *
 * [496] 下一个更大元素 I
 */
import java.util.Map;

// @lc code=start
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int n1=nums1.length;
        int[] ans=new int[n1];
        Arrays.fill(ans, -1);
        Deque<Integer> stack=new LinkedList<>();
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<n1;i++){
            map.put(nums1[i],i);
        }
        for(int i=0;i<nums2.length;i++){
            while(!stack.isEmpty()&&nums2[i]>stack.peek()){//这里我直接存值了，没有存下标
                if(map.containsKey(stack.peek())){
                    int index=map.get(stack.peek());
                    ans[index]=nums2[i];
                }
                stack.pop();
            }
            stack.push(nums2[i]);
        }
        return ans;
    }
}
// @lc code=end

